package com.dlut.java5;


import java.util.Arrays;

public class T1004_Klook {
    public static void main(String[] args) {
        int[] arr = new int[]{2,2,2,2,2};
        int ans = AmountOfCombination(arr, 8);
        System.out.println(ans);
    }

    /**
     * X X X X
     * X O O X
     * X X O X
     * X O X X
     *
     * X X X X
     * X X X X
     * X X X X
     * X O X X
     * 边界的O不变
     * @param matrix
     * @return
     */
    public static char[][] Flick(char[][] matrix) {
        //请在这里实现算法并返回翻转后的结果
        int m = matrix.length;
        int n = matrix[0].length;
        char[][] result = new char[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = 'X';
            }
        }
        for (int i = 0; i < m; i++) {
            find(matrix, result, i, 0);
            find(matrix, result, i, n-1);
        }
        for (int i = 1; i < n - 1; i++) {
            find(matrix, result, 0, i);
            find(matrix, result, m-1, i);
        }
        return result;
    }

    private static void find(char[][] matrix, char[][] result, int i, int j) {
        if (matrix[i][j] == 'O'){
            matrix[i][j] = 'X';
            result[i][j] = 'O';
            if (i>0)
                find(matrix, result, i-1, j);
            if (j>0)
                find(matrix, result, i, j-1);
            if (i< matrix.length-1)
                find(matrix, result, i+1, j);
            if (j < matrix[0].length-1)
                find(matrix, result, i, j+1);
        }
    }

    /**
     * 四数之和
     * @param nums
     * @param target
     * @return
     */
    public static int AmountOfCombination(int[] nums, int target) {
        //请在这里实现算法并返回结果
        int amount = 0;
        Arrays.sort(nums);
        int n = nums.length;
        int a=0,b=0,c=0,d=0;
        for (a = 0; a < n - 3; a++) {
            if (a>0 && nums[a] == nums[a-1]){
                continue;
            }
            for (b = a + 1; b < n - 2; b++) {
                if (b!=a+1 && nums[b] == nums[b-1]){
                    continue;
                }
                int tar = target - nums[a] - nums[b];
                c = b+1;
                d = n-1;
                while (c<d){
                    if (nums[c]+nums[d] == tar){
                        amount++;
                        c++;
                        d--;
                    }else if (nums[c]+nums[d] < tar){
                        c++;
                    }else {
                        d--;
                    }
                    while (c!=b+1 && c<n && nums[c]==nums[c-1]){
                        c++;
                    }
                    while (d!=n-1 && d>=0 && nums[d]==nums[d+1]){
                        d--;
                    }
                }
            }
        }
        return amount;
    }
}


